// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"math/bits"
)

// 用于计算支配树中最低公共祖先的代码。
// https:
// https:

// lcaRange是一种数据结构，可以计算最低的公共祖先查询
// 每个查询的预计算空间和时间分别为O（n lgn）和O（1）。
type lcaRange struct {
	// 关于每个块的附加信息（按块ID索引）。
	blocks []lcaRangeBlock

	// 范围最小查询的数据结构。
	// rangeMin[k][i]包含最小深度块的ID
	// 在从位置i到i+1的Euler巡更中，包括k-1。
	rangeMin [][]ID
}

type lcaRangeBlock struct {
	b          *Block
	parent     ID    // 支配树中的父级。0=无父项（条目或无法访问）
	firstChild ID    // 支配树中的第一个孩子
	sibling    ID    // 父母的下一个孩子
	pos        int32 // 此块出现的Euler漫游中的索引（其任何一个引用）
	depth      int32 // 支配树中的深度（根=0，其子项=1，等等）
}

func makeLCArange(f *Func) *lcaRange {
	dom := f.Idom()

	// 建树
	blocks := make([]lcaRangeBlock, f.NumBlocks())
	for _, b := range f.Blocks {
		blocks[b.ID].b = b
		if dom[b.ID] == nil {
			continue // 进入或无法到达
		}
		parent := dom[b.ID].ID
		blocks[b.ID].parent = parent
		blocks[b.ID].sibling = blocks[parent].firstChild
		blocks[parent].firstChild = b.ID
	}

	// 计算欧拉旅行顺序。
	// 每个可到达的区块将在巡演中出现#children+1次。
	tour := make([]ID, 0, f.NumBlocks()*2-1)
	type queueEntry struct {
		bid ID // 要处理的块
		cid ID // 我们正在处理的子项（0=尚未开始）
	}
	q := []queueEntry{{f.Entry.ID, 0}}
	for len(q) > 0 {
		n := len(q) - 1
		bid := q[n].bid
		cid := q[n].cid
		q = q[:n]

		// 将块添加到巡更。
		blocks[bid].pos = int32(len(tour))
		tour = append(tour, bid)

		// 继续下一个子边（如果有）。
		if cid == 0 {
			// 这是我们第一次来b。设置其深度。
			blocks[bid].depth = blocks[blocks[bid].parent].depth + 1
			// 然后探索它的第一个孩子。
			cid = blocks[bid].firstChild
		} else {
			// 我们以前见过b。探索下一个孩子。
			cid = blocks[cid].sibling
		}
		if cid != 0 {
			q = append(q, queueEntry{bid, cid}, queueEntry{cid, 0})
		}
	}

	// 计算快速范围最小查询数据结构
	rangeMin := make([][]ID, 0, bits.Len64(uint64(len(tour))))
	rangeMin = append(rangeMin, tour) // 1个大小的窗口只是巡演本身。
	for logS, s := 1, 2; s < len(tour); logS, s = logS+1, s*2 {
		r := make([]ID, len(tour)-s+1)
		for i := 0; i < len(tour)-s+1; i++ {
			bid := rangeMin[logS-1][i]
			bid2 := rangeMin[logS-1][i+s/2]
			if blocks[bid2].depth < blocks[bid].depth {
				bid = bid2
			}
			r[i] = bid
		}
		rangeMin = append(rangeMin, r)
	}

	return &lcaRange{blocks: blocks, rangeMin: rangeMin}
}

// find返回a和b的最低共同祖先。
func (lca *lcaRange) find(a, b *Block) *Block {
	if a == b {
		return a
	}
	// 在Euler漫游中查找一个箱子和一个箱子的位置。
	p1 := lca.blocks[a.ID].pos
	p2 := lca.blocks[b.ID].pos
	if p1 > p2 {
		p1, p2 = p2, p1
	}

	// 最低的公共祖先是最小深度块
	// 在从p1到p2的旅程中。我们已经预先计算了最小值
	// 深度块用于巡更的两个子序列的幂。
	// 将正确的两个预计算值组合在一起以得到答案。
	logS := uint(log64(int64(p2 - p1)))
	bid1 := lca.rangeMin[logS][p1]
	bid2 := lca.rangeMin[logS][p2-1<<logS+1]
	if lca.blocks[bid1].depth < lca.blocks[bid2].depth {
		return lca.blocks[bid1].b
	}
	return lca.blocks[bid2].b
}
